Certain architectures for the processors (CPUs) used in computers employ register as register stacks. For example, in the 64-bit architecture CPU IA-64, developed jointly by Intel Corp. and Hewlett Packard Corp., one part of general-purpose registers serves as a register stack.
For a register stack, only those registers, from among the physical registers prepared for a processor, that are required for the execution of procedures are employed as logical registers (hereinafter, in the following explanation, referred to simply as a register when there is no need to differentiate between physical registers and logical registers). For each procedure, the number of registers employed are designated and allocated by an “alloc” instruction, and when a calling source is recovered, these registers are released. In the procedures, the number of registers designated (hereinafter also referred to as “allocated”) by the alloc instruction are statically employed.
The registers in a register stack (stack registers) are employed, from the bottom to the top, as “in” arguments, local variables and “out” arguments. When a procedure has been called, an allocated “out” argument for the procedure is renamed, at the calling destination, as “in” argument.
The registers that are allocated are obtained in order by renaming a definite number of physical registers. When at allocation time there is a shortage of physical registers (a stack overflow), registers that are currently allocated are automatically restored to the memory and a new physical register is obtained. Further, when, at the time task execution is recovered by the calling source, the registers allocated to the calling source are restored to the memory (a stack underflow), restored values are automatically recovered by the registers.
Since a register stack is employed, the processing costs associated with the restoring and the recovery of registers can be avoided, so long as a stack overflow or a stack underflow does not occur.
As is described above, when a register stack is employed in the CPU architecture, the costs associated with the restoring or the recovery of registers can be avoided, so long as a stack overflow or a stack underflow does not occur.
Recently, now that CPUs that can execute instructions in parallel have become available, various register allocation methods devised to take advantage of parallel instruction processing have been proposed for inclusion in program compilation techniques. According to these methods, to reduce the parallel execution related barriers that may arise due to the occurrence of reverse dependencies or output dependencies, different registers are allocated for instructions that are executed in parallel. Therefore, the number of registers that are employed for each procedure tends to be increased.
While this method is indispensable for obtaining the parallel execution capacity of processors, the frequency whereat stack overflows or stack underflows occur is increased as the number of registers used rises. And since the cost of a stack overflow or a stack underflow is generally very high, the excessively frequent occurrence of stack overflows or of stack underflows will greatly deteriorate the execution performance of a program.
As is described above, conventionally, when a register stack is employed, the number of registers designated by the alloc instruction are statically employed for a specific procedure.
However, when another procedure is called by a specific procedure, all allocated registers are not always employed. In this case, even though there are unused registers in a stack, new registers are allocated and stack resources are wasted.